{
"cells": [
{
"cell_type": "markdown",
"id": "2a4242b5-3f32-4c5f-bbe9-5ba4f7f420bf",
"metadata": {},
"source": [
"# Handout 1\n",
"EE-556: Mathematics of Data: From Theory to Computation - Fall 2025"
]
},
{
"cell_type": "markdown",
"id": "5638e8ca-d546-4f0d-bcc6-c9949cebf6e5",
"metadata": {},
"source": [
"We review probability theory and statistics in this handout. We will also have\n",
"a basic introduction to Stochastic Gradient Descent, an extremely important\n",
"algorithm for machine learning.\n",
"\n",
"Instructor: Prof. Volkan Cevher"
]
},
{
"cell_type": "code",
"execution_count": 21,
"id": "4ebb24bf-335c-4b89-a646-e0adbdc6e8d4",
"metadata": {
"ExecuteTime": {
"end_time": "2024-07-22T08:05:15.141252Z",
"start_time": "2024-07-22T08:05:15.131251Z"
},
"execution": {
"iopub.execute_input": "2024-09-04T09:07:31.587613Z",
"iopub.status.busy": "2024-09-04T09:07:31.584790Z",
"iopub.status.idle": "2024-09-04T09:07:31.597634Z",
"shell.execute_reply": "2024-09-04T09:07:31.595031Z",
"shell.execute_reply.started": "2024-09-04T09:07:31.587502Z"
}
},
"outputs": [],
"source": [
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": 22,
"id": "f5152a9c-cb0b-41b5-8315-1cdcbd64a4a3",
"metadata": {
"ExecuteTime": {
"end_time": "2024-07-22T08:05:31.727458Z",
"start_time": "2024-07-22T08:05:31.708461Z"
},
"execution": {
"iopub.execute_input": "2024-09-04T09:07:31.862352Z",
"iopub.status.busy": "2024-09-04T09:07:31.861434Z",
"iopub.status.idle": "2024-09-04T09:07:31.879420Z",
"shell.execute_reply": "2024-09-04T09:07:31.877064Z",
"shell.execute_reply.started": "2024-09-04T09:07:31.862272Z"
}
},
"outputs": [],
"source": [
"n = 256\n",
"p = 3\n",
"sigma = 0.1\n",
"\n",
"def get_A(num=1000):\n",
" return np.random.normal(0, 1, size=(num, n, p))\n",
"\n",
"def get_w(num=1000):\n",
" return np.random.normal(0, sigma, size=(num, n))\n",
"\n",
"def get_x(num=1000):\n",
" return np.random.normal(0, 1, size=(num, p))\n",
"\n",
"def emp_vs_th(emp, th):\n",
" print(f\"Empirical: {np.mean(emp, axis=0).round(4)} +/- {np.std(emp, axis=0).round(4)} \\nTheoretical: {np.array(th).round(4)}\")"
]
},
{
"cell_type": "markdown",
"id": "2a5e4234-ed65-4b6c-9531-7c86b2f75ebc",
"metadata": {},
"source": [
"## Basic Probability\n",
"Problem 1: The Most Useful Bound in Probability Theory\n",
"\n",
"Recall the definition of a probability measure. In this problem, we will rigorously prove **the** most useful bound in probability theory, the Union Bound, stating that given any $n$ events $E_1, E_2, ..., E_n$, we have\n",
"$$\n",
"P(\\cup_{i=1}^n E_i) \\leq \\sum_{i=1}^n P(E_i).\n",
"$$\n",
"Prove the following statements.\n",
"\n",
"(a) For any two events $A$ and $B$ such that $A \\subseteq B$, prove that $P(A) \\leq P(B)$. "
]
},
{
"cell_type": "markdown",
"id": "b0f6249d-bff8-4863-948d-d86ad90cd753",
"metadata": {},
"source": [
"**Solution**:"
]
},
{
"cell_type": "markdown",
"id": "23b3ca6d-a975-4283-9413-a1ebee9f9136",
"metadata": {},
"source": [
"(b) Prove the union bound $P(\\cup_{i=1}^n E_i) \\leq \\sum_{i=1}^n P(E_i)$.\n",
"\n",
"(Hint: For any two events $E_1$ and $E_2$, prove that $P(E_1 \\cup E_2) \\leq P(E_1) + P(E_2)$. For this, you can use a useful decomposition rule of sets: $E_1 \\cup E_2 = (E_1 \\cap E_2^c) \\cup E_2$. Applying this bound recursively will finish the proof.\n",
"\n",
"To use the recursive arguments, you need to write the union of $n$ events as a union of 2 events.)"
]
},
{
"cell_type": "markdown",
"id": "69f18342-e45d-4c82-9529-fe977be65538",
"metadata": {},
"source": [
"**Solution:** "
]
},
{
"cell_type": "markdown",
"id": "393a6aed-1a10-428a-9209-8ba0ea758fa0",
"metadata": {},
"source": [
"## \"Modeling\" in the Absence of Models; Neural Networks as Universal Approximators\n",
"\n",
"Recall that the least-square estimator naturally arises from the maximum likelihood estimation of \n",
"\n",
"A1. a true signal $\\mathbf{x}^\\natural$,\n",
"\n",
"A2. with a linear model,\n",
"\n",
"A3. of added Gaussian noise.\n",
"\n",
"That is, if we assume that the data $(\\mathbf{a}_i , b_i) \n",
"% \\in (\\mathbb{R}^{p},\\mathbb{R})\n",
"\\in (\\mathbb{R}^p \\times \\mathbb{R})\n",
"$ is generated by the following relation:\n",
"\\begin{equation}\n",
"{b_i} = \\langle \\mathbf{a}_i , \\mathbf{x}^\\natural \\rangle + {\\mathbf{W}_i}, \\quad {\\mathbf{W}_i} \\sim \\mathcal{N}(0, \\sigma^2), \n",
"\\end{equation}then\n",
"\\begin{equation}\n",
"{\\mathbf{x}}^\\star_{ML} = \\underset{\\mathbf{x} \\in \\mathbb{R}^p}{\\operatorname{arg\\,min}} \\frac{1}{2}|| \\mathbf{b}- \\mathbf{A}\\mathbf{x}||_2^2\n",
"\\end{equation}where $\\mathbf{A}^\\top = [ \\mathbf{a_1}\\ \\mathbf{a_2}\\ \\cdots \\ \\mathbf{a_n} ]$.\n",
"\n",
"Although the importance of LS estimators can hardly be overemphasized, it is still widely criticized by its restrictive setting; i.e., assuming A1-3. A natural question is: What if we drop these assumptions? For instance, what if the model is nonlinear, or there is no such thing as a true signal, or the noise is far away from Gaussian?\n",
"\n",
"Neural networks [2] present a powerful framework to address these concerns with the following philosophy: First, denote the (possibly very complicated) relation between input and output by $b = h(\\mathbf{a})$, where $h$ is a function from $\\mathbb{R}^p \\rightarrow \\mathbb{R}$ and $(\\mathbf{a},b)$ follows some **unknown** distribution $\\mathbb{P}$. Then the function $h$ should satisfy\n",
"\n",
"$$\n",
"\\begin{align} \\tag{1}\n",
"h = \\underset{g}{\\operatorname{arg\\,min}} \\frac{1}{2} \\mathbb{E}_{\\mathbb{P}} \\left( g(\\mathbf{a}) - b \\right)^2, \\quad g \\text{ any function.} \n",
"\\end{align}\n",
"$$\n",
"\n",
"(**Remark:** We focus on the regression example here, while the very same idea works for classification just as well.)\n",
"\n",
"Now, there are two reasons why solving (1) is not possible:\n",
"\n",
"1. We do not know the distribution $\\mathbb{P}$; instead, we only have samples $(\\mathbf{a}_i,b_i)$ from $\\mathbb{P}$.\n",
"2. We do not know how to optimize over the set of all functions.\n",
"\n",
"For the first issue, we already know that we can replace the true average by the empirical average, leading to an empirical risk minimization problem. For the second, the key idea of deep learning relies on the following theorem [3]: Informally speaking,\n",
"\n",
"Any function $f$ can be approximated arbitrarily well by a neural network, as long as the network size is big enough.\n",
"\n",
"Combining these, we are lead to the empirical risk minimization of neural networks:\n",
"\\begin{equation}\n",
"{\\mathbf{X}}^\\star =\\underset{\\mathbf{X}}{\\operatorname{arg\\,min}} \\left\\{ \\frac{1}{n}\\sum_{i=1}^n \\left( b_i - h_{\\mathbf{X}} ( \\mathbf{a}_i ) \\right)^2 \\right\\}, \\quad h_{\\mathbf{x}}(\\mathbf{a}) = \\sigma \\left( \\mathbf{W}_k \\sigma \\left( \\cdots \\sigma\\left(\\mathbf{W}_2\\sigma \\left( \\mathbf{W}_1 \\mathbf{a} + \\boldsymbol{\\mu}_1 \\right) + \\boldsymbol{\\mu}_2 \\right) \\cdots \\right) + \\boldsymbol{\\mu}_k \\right); \\tag{2}\n",
"\\end{equation}\n",
"where $\\sigma$ is a \"proper\" activation function that requires some condition on continuity, $\\mathbf{x} = (\\mathbf{W}_1, \\boldsymbol{\\mu}_1, \\mathbf{W}_2, \\boldsymbol{\\mu}_2, \\dots, \\mathbf{W}_k, \\boldsymbol{\\mu}_k)$, $\\mathbf{W}_i \\in \\mathbb{R}^{d_i\\times d_{i-1}}$, $\\boldsymbol{\\mu}_i \\in \\mathbb{R}^{d_i}$ and $\\mathbf{a}\\in\\mathbb{R}^p$ (more on the notation in the lectures).\n",
"The hope is that, as long as we have enough parameters and data, the learned neural network is a good approximator for the function $h$:\n",
"$$\n",
"h_{{\\mathbf{x}}^\\star} \\simeq h,\n",
"$$\n",
"\n",
"which is true by the theorem of [3]. There are however trade-offs involved in scaling up over-parametrized networks: width helps robustness; depth helps robustness under a certain initialization but hurts it under another [5].\n",
"\n",
"In conclusion, \n",
"\n",
"Neural networks can be viewed as a \"universal modeling\" scheme where no assumption about the data distribution is made.\n",
"\n",
"\n",
"\n",
"Finally, all the above reasoning relies on the big \"if\" that we can optimize (2). It is an important fact that one can efficiently compute the (stochastic) **gradients** of (2) via the so-called *backpropagation* [4], and therefore one can run first-order algorithms. The details will be covered in the coming lectures and exercises."
]
},
{
"cell_type": "markdown",
"id": "2397e9f0-6797-469d-bb83-89a652b1d065",
"metadata": {},
"source": [
"## Randomness in Statistical Learning Problems, and Stochastic Gradient Descent\n",
"\n",
"Problem 3: Recognizing Different Randomness\n",
"\n",
"There are many different randomness in modern data science or machine learning problems. The purpose of this exercise is to help you get a deeper understanding of them.\n",
"\n",
"This course is all about inferring from data, and the data from real world is often random. Besides this intrinsic randomness, another common source of randomness in modern applications is the *randomized algorithms*. It is extremely important that you have a clear picture of what randomness is truly relevant for statistical inference, and what is only for computational purposes.\n",
"\n",
"Consider the Gaussian linear model from Lecture 1: Let $\\mathbf{x}^\\natural \\in \\mathbb{R}^p$ and $\\mathbf{A} \\in \\mathbb{R}^{n\\times p}$. We have observations of the form\n",
"\n",
"\\begin{equation}\n",
"\\mathbf{b} = \\mathbf{A}\\mathbf{x}^\\natural + \\mathbf{w}, \\tag{3}\n",
"\\end{equation}where $\\mathbf{w} \\sim \\mathcal{N}(0, \\sigma^2I)$ is the Gaussian noise vector. We aim to solve the maximum likelihood estimator \n",
"\n",
"\\begin{equation}\n",
"{\\mathbf{x}}^\\star_{ML} = \\underset{x \\in \\mathbb{R}^p}{\\operatorname{arg\\,min}} \\left \\{ f(\\mathbf{X}):= \\frac{1}{2n}|| \\mathbf{b}- \\mathbf{A}\\mathbf{x}||_2^2\\right\\}, \\tag{4}\n",
"\\end{equation} \n",
"\n",
"where we have normalized the the loss function by the number of measurements $n$ (the number $\\frac{1}{2}$ is just for convenience later).\n",
"\n",
"\n",
"(a) So far the only random component is the noise $\\mathbf{w}$. Let $\\mathbb{E}_{\\mathbf{w}}$ denote the expectation with respect to the randomness of $\\mathbf{w}$. Compute $\\mathbb{E}_{\\mathbf{w}}||\\mathbf{b} -\\mathbf{A} \\mathbf{x}^\\natural ||_2^2$."
]
},
{
"cell_type": "markdown",
"id": "bc7a91a1-e85c-4aa3-8944-0a96e8588b93",
"metadata": {},
"source": [
"**Solution:**"
]
},
{
"cell_type": "markdown",
"id": "118feb15-4d15-4717-bae3-d5d8dd7633b6",
"metadata": {},
"source": [
"### Try verifying the result with code!"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "aa5fc8d5-4b88-4e70-b22c-cfe0a2ef8ed2",
"metadata": {
"ExecuteTime": {
"end_time": "2024-07-22T08:05:32.674509Z",
"start_time": "2024-07-22T08:05:32.598461Z"
}
},
"outputs": [],
"source": [
"A, x = get_A(1)[0], get_x(1)[0]\n",
"w = get_w()\n",
"b = A @ x + w\n",
"\n",
"emp = np.linalg.norm(b - A @ x, axis=1) ** 2\n",
"th = n * sigma ** 2\n",
"emp_vs_th(emp, th)"
]
},
{
"cell_type": "markdown",
"id": "dc009cf5-ad86-4559-9a29-03706d5bb732",
"metadata": {},
"source": [
"(b) In practice, the measurement matrix $\\mathbf{A}$ is often random. Assume that the entries of $\\mathbf{A}$ are independent random variables with mean 0 and variance 1, and are independent of the noise $\\mathbf{w}$. Let $\\mathbb{E}_{\\mathbf{A}}$ denote the expectation with respect to the randomness of $\\mathbf{A}$. Show that\n",
"\\begin{equation}\n",
"\\frac{1}{n} \\mathbb{E}_{A} ||\\mathbf{A}\\mathbf{x}||_2^2 = ||\\mathbf{x}||_2^2\n",
"\\end{equation}for all $\\mathbf{x} \\in \\mathbb{R}^p$.\n",
"\n",
"(Hint: Let $\\mathbf{a^\\top_i}$ be a row of $\\mathbf{A}$. What is $\\mathbb{E}_{\\mathbf{A}}|\\langle \\mathbf{a_i}, \\mathbf{x} \\rangle|^2$? Can you compute $\\mathbb{E}_{\\mathbf{A}} ||\\mathbf{A}\\mathbf{x}||_2^2$ through $\\mathbb{E}_{\\mathbf{A}}|\\langle \\mathbf{a_i}, \\mathbf{x} \\rangle|^2$?)"
]
},
{
"cell_type": "markdown",
"id": "57e82392-c696-4019-b061-f639f30a9a0c",
"metadata": {},
"source": [
"**Solution:**"
]
},
{
"cell_type": "markdown",
"id": "ebd20b40-aced-4281-8111-bfe087054227",
"metadata": {},
"source": [
"### Try verifying the result with code!"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a4cd2b00-481b-4eb1-a13e-e1c87e820455",
"metadata": {
"ExecuteTime": {
"end_time": "2024-07-22T08:05:39.907041Z",
"start_time": "2024-07-22T08:05:39.864044Z"
}
},
"outputs": [],
"source": [
"A, x = get_A(), get_x(1)[0]\n",
"emp = ???\n",
"th = ???\n",
"emp_vs_th(emp, th)"
]
},
{
"cell_type": "markdown",
"id": "a0eacac8-129b-42c6-b8e6-416071a3f34a",
"metadata": {},
"source": [
"(c) Show that the following useful basic inequality holds:\n",
"\\begin{equation}\n",
"||\\mathbf{A}({\\mathbf{x}}^\\star_{ML} - \\mathbf{x}^\\natural) ||_2^2 \\leq 2\\langle \\mathbf{w}, \\mathbf{A}({\\mathbf{x}}^\\star_{ML} - \\mathbf{x}^\\natural) \\rangle.\n",
"\\end{equation}\n",
"(Hint: The maximum likelihood estimator minimizes the loss function, so you can compare the values of the loss function when substituting in ${\\mathbf{x}}^\\star_{ML}$ and any other $\\mathbf{x}$.)"
]
},
{
"cell_type": "markdown",
"id": "0ef3e683-6c82-4952-86f9-bfb176d6e199",
"metadata": {},
"source": [
"**Solution:**"
]
},
{
"cell_type": "markdown",
"id": "844d26f9-97e8-457f-bc8d-6505d7371c6f",
"metadata": {},
"source": [
"(d) What we ultimately care about is the estimation error: $\\mathbb{E}_{\\mathbf{A}, \\mathbf{w}}||{\\mathbf{x}}^\\star_{ML} - \\mathbf{x}^\\natural ||_2^2.$ In view of (b) and (c), one might be tempted to conclude that \n",
"\\begin{equation}\n",
"\\mathbb{E}_{\\mathbf{A}, \\mathbf{w}}||{\\mathbf{x}}^\\star_{ML} - \\mathbf{x}^\\natural ||_2^2 \\leq 2\\mathbb{E}_{\\mathbf{A}, \\mathbf{w}}\\langle \\mathbf{w}, \\frac{1}{n}\\mathbf{A}({\\mathbf{x}}^\\star_{ML} - \\mathbf{x}^\\natural) \\rangle.\n",
"\\end{equation}Please argue carefully why this argument is NOT true.\n",
"(Hint: In part (b) we considered a fixed, deterministic $\\mathbf{x}$. Is ${\\mathbf{x}}^\\star_{ML} - \\mathbf{x}^\\natural$ deterministic? If not, what randomness does it depend on?)"
]
},
{
"cell_type": "markdown",
"id": "05282f01-2049-4cbf-8a14-3b60aca56ae1",
"metadata": {},
"source": [
"**Solution:**"
]
},
{
"cell_type": "markdown",
"id": "18615700-7739-4afc-aa7a-bbb3ffe597c1",
"metadata": {},
"source": [
"(e) We introduce the important Stochastic Gradient Descent (SGD) in the exercise.\n",
"\n",
"Recall Gradient Descent (GD) for minimizing (4):\n",
"\n",
"- Choose $\\mathbf{x}_0$ arbitrarily.\n",
"- Do $\\mathbf{x}_{k+1} = \\mathbf{x}_k - \\alpha_k \\nabla f(\\mathbf{x}_k)$ for some predetermined step-sizes $\\alpha_k>0$.\n",
"\n",
"Recall also that for (4), the gradient at a point $\\mathbf{x}$ is $\\nabla f(\\mathbf{x})= \\frac{1}{n}\\mathbf{A}^\\top(\\mathbf{A}\\mathbf{x}-\\mathbf{b})$.\n",
"\n",
"Consider a randomized algorithm as follows. At the current iterate $\\mathbf{x}_k$, an index $i \\in \\{1, 2, ..., n\\}$ is selected uniformly at random. We then replace the gradient at $\\mathbf{x}_k$ by the vector $(\\langle \\mathbf{a_i}, \\mathbf{x}_k\\rangle - b_i)\\mathbf{a_i}$, where $\\mathbf{a^\\top_i}$ is the $i$-th row of $A$ and $b_i$ is the $i$-th element of $\\mathbf{b}$. All other steps are the same as GD. Let $\\mathbb{E}_{SGD}$ denote the expectation with respect to the randomness of this algorithm. Show that\n",
"\n",
"\\begin{equation}\n",
"\\mathbb{E}_{SGD}\\left(\\langle \\mathbf{a_i}, \\mathbf{x}_k\\rangle - b_i\\right)\\mathbf{a_i} = \\frac{1}{n}\\mathbf{A}^\\top(\\mathbf{A}\\mathbf{x}_k-\\mathbf{b}).\n",
"\\end{equation} That is, the algorithm is a randomized version of Gradient Descent, hence the name.\n",
"(Hint: Recall that $\\mathbf{a^\\top_i}$ is a row of $\\mathbf{A}$, and therefore it is a column of $\\mathbf{A}^\\top$.)\n",
"\n",
"\n",
"*Remark:* There are many reasons for using SGD instead of GD; we refer the interested students to [1] for a gentle introduction of SGD. Please do bear in mind that SGD is extremely important in practice. Ever heard of deep learning? AlphaGo? Your interest might be piqued if you know that SGD is the go-to algorithm for these state-of-the-art learning machines."
]
},
{
"cell_type": "markdown",
"id": "1f75de1c-4db5-4687-bdff-c95eb77f674c",
"metadata": {},
"source": [
"**Solution:**"
]
},
{
"cell_type": "markdown",
"id": "3bfc3d6e-cce4-4ec3-bf72-a3d5b6b4c340",
"metadata": {},
"source": [
"### Try verifying the result with code!"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c1fae3b2-7d4e-4754-bbbd-4ef88c0cd774",
"metadata": {
"ExecuteTime": {
"end_time": "2024-07-22T08:18:06.532981Z",
"start_time": "2024-07-22T08:18:06.496983Z"
}
},
"outputs": [],
"source": [
"A, x = get_A(1)[0], get_x(1)[0]\n",
"w = get_w(1)[0]\n",
"b = A @ x + w\n",
"\n",
"x_sgd = np.zeros(p)\n",
"i_batch = np.random.choice(n, size=1000)\n",
"emp = ???\n",
"th = ???\n",
"emp_vs_th(emp, th)"
]
},
{
"cell_type": "markdown",
"id": "94f0762e-55e0-469a-9023-cbb3cfdabee4",
"metadata": {},
"source": [
"(f) Under the assumptions in (b), show that \n",
"\\begin{equation}\n",
"\\mathbb{E}_{\\mathbf{A}, \\mathbf{w}}\\left(\\langle \\mathbf{a_i}, \\mathbf{x} \\rangle - b_i\\right)\\mathbf{a_i} = \\mathbf{x}-\\mathbf{x}^\\natural\n",
"\\end{equation} for any $\\mathbf{x}$."
]
},
{
"cell_type": "markdown",
"id": "185b561c-42a7-43a5-9536-c24d2b362a3f",
"metadata": {},
"source": [
"**Solution:**"
]
},
{
"cell_type": "markdown",
"id": "586e46ca-9d68-40c2-a817-966026c47a22",
"metadata": {},
"source": [
"### Try verifying the result with code!"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "467185ec-948b-49ff-9438-f98cc94915e9",
"metadata": {
"ExecuteTime": {
"end_time": "2024-07-22T08:05:54.165992Z",
"start_time": "2024-07-22T08:05:54.116029Z"
}
},
"outputs": [],
"source": [
"A, x = get_A(), get_x(1)[0]\n",
"w = get_w()\n",
"b = A @ x + w\n",
"\n",
"x_sgd = get_x(1)[0]\n",
"i = np.random.choice(n, size=1)[0]\n",
"\n",
"emp = ???\n",
"th = ???\n",
"emp_vs_th(emp, th)"
]
},
{
"cell_type": "markdown",
"id": "a26748a8-2749-4a0d-ac88-08f0c2f59504",
"metadata": {},
"source": [
"(g) Under the assumptions in (b), show that, for any $\\mathbf{x}$, \n",
"\\begin{equation}\n",
"\\frac{1}{n}\\mathbb{E}_{\\mathbf{A}, \\mathbf{w}}\\mathbf{A}^\\top(\\mathbf{A}\\mathbf{x}-\\mathbf{b}) = \\mathbf{x}-\\mathbf{x}^\\natural.\n",
"\\end{equation}\n",
"\n",
"(Hint: There are many ways of proving this. Combining (e) and (f) gives a very simple proof.)"
]
},
{
"cell_type": "markdown",
"id": "b7c9b17b-8bc4-4497-9aa5-e3259c35157b",
"metadata": {},
"source": [
"**Solution:**"
]
},
{
"cell_type": "markdown",
"id": "f73d2b14-ac6f-451d-8850-8803686ead1c",
"metadata": {},
"source": [
"### Try verifying the result with code!"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6faef4a4-dd6b-4c39-9ec1-6b9c8993a810",
"metadata": {
"ExecuteTime": {
"end_time": "2024-07-22T08:05:55.096992Z",
"start_time": "2024-07-22T08:05:55.039996Z"
}
},
"outputs": [],
"source": [
"A, x = get_A(), get_x(1)[0]\n",
"w = get_w()\n",
"b = A @ x + w\n",
"\n",
"x_sgd = get_x(1)[0]\n",
"emp = ???\n",
"th = ???\n",
"emp_vs_th(emp, th)"
]
},
{
"cell_type": "markdown",
"id": "32c397e5-a12e-4e5b-9aa4-5daf1d02e163",
"metadata": {},
"source": [
"## Multinomial logistic regression and language model training\n",
"\n",
"Problem 4: Towards training language models\n",
"\n",
"Recall that in the lecture we talk about logistic regression for binary classification problems. Let $\\mathbf{x}^\\natural \\in \\mathbb{R}^p$. Let $\\mathbf{a}_1, \\ldots, \\mathbf{a}_n \\in \\mathbb{R}^p$ be given. The sample is given by $\\mathbf{b} := ( b_1, \\ldots, b_n ) \\in \\left\\{ 0, 1 \\right\\}^n$. The classifier $h_\\mathbf{X}$ estimates the probability $P(b = 1)$ by outputing a scalar $h_\\mathbf{X}$ such that $h_\\mathbf{X}:= \\left[ 1 + \\exp \\left( - \\left\\langle \\mathbf{a}_i, \\mathbf{x} \\right\\rangle \\right) \\right]^{-1} = P(b = 1)$.\n",
"\n",
"(a) Show that maximizing the likelihood is equivalent to minimizing the cross-entropy between the real distribution and estimated distribution."
]
},
{
"cell_type": "markdown",
"id": "33a61ea3-3f6b-46a0-b30a-26d43e458635",
"metadata": {},
"source": [
"**Solution:**"
]
},
{
"cell_type": "markdown",
"id": "981d5abb-6d27-4a01-ab73-b8c6d3d6e054",
"metadata": {},
"source": [
"(b) In logistic regression, we only deal with two classes. But in reality, there are many situations where multiple classes are involved. In this case, we need to generalize the logistic regression to multinomial logistic regression (sometimes called the softmax regression). \n",
"\n",
"Suppose there are $K$ classes ($K\\ge2$). The classifier aims to output a vector $\\mathbf{h}_\\mathbf{X} \\in \\mathbb{R}^K$ to estimate the probability of each class such that its $k$ element is $ P(b = k|\\mathbf{a})$.\n",
"Note that in this case, the classifier is parameterized by a learnable matrix $\\mathbf{X} \\in \\mathbb{R}^{K \\times p}$ to estimate the probability as follows: $P(b = k|\\mathbf{a} ) = (\\text{Softmax}(\\mathbf{X} \\mathbf{a}))^{[k]}, \\text{for } k \\in [K]$, where Softmax is defined by:\n",
"$$ \\text{Softmax}(\\mathbf{X} \\bf \\mathbf{a}) = \\begin{bmatrix} \n",
" \\frac{\\exp{((\\mathbf{X} \\bf \\mathbf{a})^{[1]})}}\n",
" {\n",
" \\sum_{i=1}^{K}\n",
" \\exp{((\\mathbf{X} \\mathbf{a})^{[i]})}\n",
" }\n",
" \\\\ \\vdots \\\\\n",
" \\frac{\\exp{((\\mathbf{X} \\mathbf{a})^{[K]})}}\n",
" {\n",
" \\sum_{i=1}^{K}\n",
" \\exp{((\\mathbf{X} \\mathbf{a})^{[i]})}\n",
" }\n",
"\\end{bmatrix} \\in R^K.$$\n",
"\n",
"Again, show that maximizing the likelihood is equivalent to minimizing the cross entropy between the real distribution and the estimated\n",
"distribution."
]
},
{
"cell_type": "markdown",
"id": "0ec1d29d-401d-487f-a576-98bb92c0cfd2",
"metadata": {},
"source": [
"**Solution:**"
]
},
{
"cell_type": "markdown",
"id": "5bd00ce4-b334-4530-9cec-64b0d8a5121d",
"metadata": {},
"source": [
"(c) To some extent, training a language model is essentially tackling a multinomial logistic regression problem where the model needs to predict next word given previous words. \n",
"A neural network $\\mathbf{h}_{\\mathbf{X}}$ parameterized by $\\mathbf{X}$ is used as an ML estimator, as mentioned in the lecture. Specifically, $\\mathbf{h}_{\\mathbf{X}}$ aims to predict the $t$ token given $t-1$ tokens.\n",
"\\begin{equation*}\n",
" \\begin{split}\n",
" & \n",
" \\min_{\\mathbf{X}}\n",
" - \\log \\text{p}_{\\mathbf{X}} (\\mathbf{b}_{1:T})=\n",
" - \\log \\left( \n",
" \\prod_{t=1}^{T} \\text{p}_{\\mathbf{X}}(\\mathbf{b}_t|\\mathbf{b}_{1:t-1})\n",
" \\right) \n",
" = \n",
" \\sum_{t=1}^{T} \\left(\n",
" -\\log \\text{p}_{\\mathbf{X}}(\\mathbf{b}_t|\\mathbf{b}_{1:t-1})\n",
" \\right)\n",
" \\\\ & = \t\t\n",
" \\sum_{t=1}^{T} \\left(\n",
" -\\log \\mathbf{h}_{\\mathbf{X}}(\\mathbf{b}_{1:t-1})^{[\"\\mathbf{b}_t\"]}\n",
" \\right)\n",
" = \\text{cross entropy loss}.\n",
" \\end{split}\n",
"\\end{equation*}\n",
"\n",
"\n",
"Write down the SGD algorithm for training a language model given a corpus that consists of $n$ sentences."
]
},
{
"cell_type": "markdown",
"id": "383dddee-082a-4bd7-9c7f-ce2c2fc7cb90",
"metadata": {},
"source": [
"**Solution:**"
]
},
{
"cell_type": "markdown",
"id": "877bd3fe-6197-48be-b4e3-7429025e531a",
"metadata": {},
"source": [
"## References \n",
"\n",
"[1] LÉON BOTTOU Stochastic Gradient Descent Tricks, Neural Networks: Tricks of the Trade, page 421-436, Springer 2012.\n",
"\n",
"[2] SIMON HAYKIN Neural networks: a comprehensive foundation, Prentice Hall PTR 1994.\n",
"\n",
"[3] ANDREW BARRON Universal approximation bounds for superpositions of a sigmoidal function, IEEE Transactions on Information theory,\n",
"1993.\n",
"\n",
"[4] DAVID RUMELHART, GEOFFREY HINTON, AND RONALD WILLIAMS Learning representations by back-propagating errors, Cognitive\n",
"modeling, 1988.\n",
"\n",
"[5] Zhu, Z., Liu, F., Chrysos, G. & Cevher, V. Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization).\n",
"ArXiv Preprint ArXiv:2209.07263. (2022)\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.5"
},
"latex_envs": {
"LaTeX_envs_menu_present": true,
"autoclose": false,
"autocomplete": true,
"bibliofile": "biblio.bib",
"cite_by": "apalike",
"current_citInitial": 1,
"eqLabelWithNumbers": true,
"eqNumInitial": 1,
"hotkeys": {
"equation": "Ctrl-E",
"itemize": "Ctrl-I"
},
"labels_anchors": false,
"latex_user_defs": false,
"report_style_numbering": false,
"user_envs_cfg": false
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
},
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
},
"widgets": {
"application/vnd.jupyter.widget-state+json": {
"state": {},
"version_major": 2,
"version_minor": 0
}
}
},
"nbformat": 4,
"nbformat_minor": 5
}